package com.搜索和回溯;

class Solution12 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //终止条件
        if(root==null||root==p||root==q) return root;
        //递推
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //返回值,分成四种情况
        if(left==null && right==null) return null;
        if(left==null) return right;
        if(right==null) return left;
        return root;
}
}

public class 剑指Offer68II二叉树的最近公共祖先 {
    public static void main(String[] args) {

    }
}
